class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}
export default class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  // 插入新的键
  insert(key) {
    let newNode = new Node(key);
    if (this.root == null) {
      this.root = newNode;
    } else {
      BinarySearchTree.insertNode(newNode, this.root);
    }
  }
  // 查找键
  search(key) {
    // let node = this.root;
    // while (node != null) {
    //   if (key > node.key) {
    //     node = node.right;
    //   } else if (key < node.key) {
    //     node = node.left;
    //   } else {
    //     return node;
    //   }
    // }
    // return null;
    return BinarySearchTree.serachNode(key, this.root);
  }
  // 中序遍历
  inOrderTraverse(handler) {
    BinarySearchTree.inOrderTraverseNode(this.root, handler);
  }
  // 先序遍历
  preOrderTraverse(handler) {
    BinarySearchTree.preOrderTraverseNode(this.root, handler);
  }
  // 后序遍历
  postOrderTraverse(handler) {
    BinarySearchTree.postOrderTraverseNode(this.root, handler);
  }
  // 最小值
  min() {
    let node = this.root,
      key = null;
    while (node != null) {
      key = node.key;
      node = node.left;
    }
    return key;
  }
  // 最大值
  max() {
    let node = this.root,
      key = null;
    while (node != null) {
      key = node.key;
      node = node.right;
    }
    return key;
  }
  // 删除键
  remove(key) {
    let current = this.root,
      parent = null,
      isLeftChild = true;
    while (current.key != key) {
      parent = current;
      if (key < current.key) {
        isLeftChild = true;
        current = current.left;
      } else {
        isLeftChild = false;
        current = current.right;
      }
      // 找到最后 没有找到
      if (current == null) return false;
    }
    // 1 叶子节点
    if (current.left == null && current.right == null) {
      // 根节点 切是叶子节点
      if (current == this.root) {
        this.root = null;
      } // 左
      else if (isLeftChild) {
        parent.left = null;
      } // 右
      else {
        parent.right = null;
      }
    }
    // 2 一个子节点
    else if (current.left == null) {
      if (current == this.root) {
        this.root = current.left;
      } else if (isLeftChild) {
        parent.left = current.left;
      } else {
        parent.right = current.left;
      }
    } else if (current.right == null) {
      if (current == this.root) {
        this.root = current.right;
      } else if (isLeftChild) {
        parent.left = current.right;
      } else {
        parent.right = current.right;
      }
    }
    // 3 二个子节点
    else {
      // 后继方法删除
      // let successor = BinarySearchTree.successorNode(current);
      // if (current == this.root) {
      //   this.root = successor;
      // } else if (isLeftChild) {
      //   parent.left = successor;
      // } else {
      //   parent.right = successor;
      // }
      // successor.left = current.left;
      // 前驱方法删除
      let predecessor = BinarySearchTree.predecessorNode(current);
      if (current == this.root) {
        this.root = predecessor;
      } else if (isLeftChild) {
        parent.left = predecessor;
      } else {
        parent.right = predecessor;
      }
      predecessor.right = current.right;
    }
  }
  static insertNode(newNode, node) {
    if (newNode.key < node.key) {
      if (node.left == null) {
        node.left = newNode;
      } else {
        BinarySearchTree.insertNode(newNode, node.left);
      }
    } else {
      if (node.right == null) {
        node.right = newNode;
      } else {
        BinarySearchTree.insertNode(newNode, node.right);
      }
    }
  }
  static preOrderTraverseNode(node, handler) {
    if (node != null) {
      handler(node.key);
      BinarySearchTree.preOrderTraverseNode(node.left, handler);
      BinarySearchTree.preOrderTraverseNode(node.right, handler);
    }
  }
  static inOrderTraverseNode(node, handler) {
    if (node != null) {
      BinarySearchTree.inOrderTraverseNode(node.left, handler);
      handler(node.key);
      BinarySearchTree.inOrderTraverseNode(node.right, handler);
    }
  }
  static postOrderTraverseNode(node, handler) {
    if (node != null) {
      BinarySearchTree.postOrderTraverseNode(node.left, handler);
      BinarySearchTree.postOrderTraverseNode(node.right, handler);
      handler(node.key);
    }
  }
  static serachNode(key, node) {
    if (key > node.key) {
      node = node.right;
    } else if (key < node.key) {
      node = node.left;
    } else {
      return node;
    }
    return BinarySearchTree.serachNode(key, node);
  }
  // 前驱
  static predecessorNode(node) {
    let predecessor = node,
      current = node.left,
      predecessorParent = null;
    while (current != null) {
      predecessorParent = predecessor;
      predecessor = current;
      current = current.right;
    }
    if (predecessor != node.left) {
      predecessorParent.right = predecessor.left;
      predecessor.left = node.left;
    }
    return predecessor;
  }
  // 后继
  static successorNode(node) {
    let successor = node,
      current = node.right,
      successorParent = null;
    while (current != null) {
      successorParent = successor;
      successor = current;
      current = current.left;
    }
    if (successor != node.right) {
      successorParent.left = successor.right;
      successor.right = node.right;
    }
    return successor;
  }
}
